package m202405.d17;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/17 14:14
 */
public class Q1143 {

    /**
     * dp[i][j] 表示text1(0-i)和text2(0-j)的最长公共自序列长度
     * <p>
     * dp[i][j] = max(dp[i-1][j],dp[i][j-1])  text1(i-1) != text1(j-1)
     * dp[i][j] = dp[i-1][j-1]+1  text1(i-1) == text1(j-1)
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i < text1.length() + 1; i++) {
            char t1 = text1.charAt(i-1);
            for (int j = 1; j < text2.length() + 1; j++) {
                char t2 = text2.charAt(j-1);
                if (t1 == t2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }

}
